package Offer_53_1;

import java.util.Arrays;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2023/3/31 12:26
 * 剑指 Offer 53 - I. 在排序数组中查找数字
 *  通过二分查找，分别找到左右边界， 再对输入的数据合法性判断，返回 right- left +1 的到结果
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {1};
        search(nums,1);
    }
    public static int search(int[] nums, int target) {
        int left = getFirstIndex(nums,target);
        int right = getLastIndex(nums,target);
        if (left >= 0 && left <= right && right < nums.length && nums[left] == target && nums[right] == target){
            return right - left + 1;
        }
        return 0;
    }

    private static int getLastIndex(int[] nums, int target) {
        int left = 0 ;
        int right = nums.length-1;
        int res = -1;
        while (left<=right){
            int mid = left+(right-left)/2;
            if (nums[mid] > target){
                right = mid -1;
            }else if (nums[mid] < target){
                left = mid +1;
            }else {
                res = mid;
                left = mid + 1;
            }
        }
        return res;
    }

    private static int getFirstIndex(int[] nums, int target) {
        int left = 0 ;
        int right = nums.length-1;
        int res = -1;
        while (left<=right){
            int mid = left+(right-left)/2;
            if (nums[mid] > target){
                right = mid -1;
            }else if (nums[mid] < target){
                left = mid +1;
            }else {
                res = mid;
                right = mid - 1;
            }
        }
        return res;
    }

}
